package fun.coding.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Anagrams {

	public static void main(String[] args) {
		Anagrams instance = new Anagrams();
		System.out.println(instance.sortString("bca"));
	}
	
	/**
	 * Given an array of strings, return all groups of strings that are anagrams.
		Note: All inputs will be in lower-case.
		
		It is not very well stated that the outputs don't need to be a set, could be dups
		e.g., "a", "a" returns "a", "a"
	 */
	public List<String> anagrams(String[] strs) {
		List<String> res = new LinkedList<String>();
		if (strs == null || strs.length == 0) return res;
		
		Map<String, List<String>> lookup = new HashMap<String, List<String>>();
		
		for (String s : strs) {
			String sortedString = sortString(s);
			if (lookup.containsKey(sortedString)) {
				lookup.get(sortedString).add(s);
			} else {
				List<String> l = new ArrayList<String>();
				l.add(s);
				lookup.put(sortedString, l);
			}
		}
		
		for (List<String> l : lookup.values()) {
			if (l.size() > 1) {
				res.addAll(l);
			}
		}
		
		return res;
	}
	
	public String sortString(String s) {
		char[] a = s.toCharArray();
		Arrays.sort(a);
		// Need to create a new instance
		return new String(a);
	}
	
	public List<String> anagramsTimeExceed(String[] strs) {
		List<String> res = new LinkedList<String>();
		Set<String> resSet = new HashSet<String>();
		if (strs == null || strs.length == 0) return res;
		
		for (int i = 0; i < strs.length; i++) {
			// Even with this, still TLE since it is O(N^2)
			if (resSet.contains(strs[i])) continue;
			for (int j = i + 1; j < strs.length; j++) {
				if (resSet.contains(strs[j])) continue;
				
				if (this.isAnagram(strs[i], strs[j])) {
					resSet.add(strs[i]);
					resSet.add(strs[j]);
				}
			}
		}
		
		res.addAll(resSet);
		return res;
	}
	
	private boolean isAnagram(String s1, String s2) {
		if (s1 == null || s2 == null) return false;
		
		Map<Character, Integer> lookup = new HashMap<Character, Integer>();
		
		for (int i = 0; i < s1.length(); i++) {
			char c = s1.charAt(i);
			lookup.put(c, lookup.containsKey(c) ? lookup.get(c) + 1 : 1);
		}
		
		for (int i = 0; i < s2.length(); i++) {
			char c = s2.charAt(i);
			if (!lookup.containsKey(c)) return false;
			
			int value = lookup.get(c);
			if (value == 0) return false;
			lookup.put(c, value - 1);
		}
		
		for (Integer i : lookup.values()) {
			if (i > 0) return false;
		}
		
		return true;
	}

}
